package com.bauer.base.datastructure.tree.bminus;

/**
 * @Author ：rui.wei
 * @Date ：Created in 14:44 2019/7/31
 * @Description：
 * B- 树 定义
 * 1） 根结点的孩子数>=2(前提是树高度大于1)
 * 2） 除根结点与叶子结点，其他结点的孩子数为[ceil(m/2),m]个。ceil函数表示上取整数
 * 3） 所有叶子结点都出现在同一层，叶子结点不存储数据。
 * 4） 各个结点包含n个关键字信息：(P0,K1,P1,K2,P2......Kn,Pn) 其中：
 *  4.1) Ki(i=1,2......n)为关键字，且K(i-1)<Ki，即从小到大排序
 *  4.2) 关键字的个数n必须满足：[ceil(m/2)-1,m-1]
 *  4.3) Pi指向子树，且指针P(i-1)所指向的子树结点中所有关键字均小于Ki。即：父结点中任何关键字的左孩子都小于它，右孩子大于它。
 *
 * 增加节点
 * 1）插入新元素，如果叶子结点空间足够，则插入其中，遵循从小到大排序；
 * 2）如果该结点空间满了，进行分裂。将该结点中一半关键字分裂到新结点中，中间关键字上移到父结点中。
 *
 * 删除节点
 * 1）查找B-tree中需删除的元素,如果该元素在B-tree中存在，则将该元素在其结点中进行删除。
 * 2）删除该元素后，判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的相近元素到父节点中（相近元素指的是：刚被删除元素的相邻后继元素，比如删除D，相近元素就是F等）
 * 3）然后接着判断：如果结点中元素个数小于ceil(m/2)-1，首先找其相邻兄弟结点元素是否足够（结点中元素个数大于ceil(m/2)-1），如果足够，向父节点借一个元素，同时将借的元素的孩子结点中相邻后继元素上移到父结点中；
 * 如果其相邻兄弟都不够，即借完之后其结点元素个数小于ceil(m/2)-1，那进行合并，具体是：将父结点中元素下移到要合并结点中（该元素一般是位于两个合并结点的中间元素），然后进行合并。 4）以上操作按顺序进行递归执行
 */
public class BminusTreeDemo {


    public static void main(String[] args) {
        int[] test = new int[]{3, 14, 7, 1, 8, 5, 11, 17, 13, 6, 23, 12, 20, 26, 4, 16, 18, 24, 25, 19};
        BminusTreeNode treeNode = new BminusTreeNode(5);
        for (int k : test) {

            BminusNode bminusNode = putdata(new BminusNode(k), treeNode);
            if (bminusNode != null) {
                treeNode = new BminusTreeNode(treeNode.getM());
                treeNode.put(bminusNode);
            }
        }
        pringData(treeNode);

    }

    public static void pringData(BminusTreeNode bminusTreeNode) {
        if (bminusTreeNode == null) {
            return;
        }
        for (BminusNode bminusNode : bminusTreeNode.getDataNodes()) {
            System.out.println(bminusNode.getData());
            pringData(bminusNode.getLeft());
            pringData(bminusNode.getRight());
        }
    }


    public static BminusNode putdata(BminusNode dataNode, BminusTreeNode treeNode) {

        BminusTreeNode treeNode1 = null;
        if (dataNode.getLeft() == null) {
            treeNode1 = treeNode.getBminusTreeNode(dataNode.getData());
        } else {
            treeNode1 = treeNode;
        }

        if (treeNode1 != treeNode) {
            BminusNode retrunValue = putdata(dataNode, treeNode1);
            if (retrunValue != null) {
                return putdata(retrunValue, treeNode);
            } else {
                return null;
            }
        }

        if (treeNode.size() < 4) {
            treeNode.put(dataNode);
            return null;
        }
        if (treeNode.size() == 4) {
            treeNode.put(dataNode);
            BminusNode bminusNode = new BminusNode(treeNode.getMid().getData(), treeNode.getLeft(),
                    treeNode.getRight());
            return bminusNode;
        }

        return null;

    }

}
